// 222. 完全二叉树的节点个数
// 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
// 思路：用递归，如果节点为空就返回
 var countNodes = function(root) {
    const nodeNums=function(root){
        let leftNode=0,rightNode=0;
        if(root===null) return 0;
        leftNode=nodeNums(root.left);
        rightNode=nodeNums(root.right);
        return leftNode+rightNode+1;
    }
    return nodeNums(root);

};
var countNodes = function(root) {
    //层序遍历
    let queue=[];
    if(root===null){
        return 0;
    }
    queue.push(root);
    let nodeNums=0;
    while(queue.length){
        let length=queue.length;
        while(length--){
            let node=queue.shift();
            nodeNums++;
            node.left&&queue.push(node.left);
            node.right&&queue.push(node.right);
        }
    }
    return nodeNums;
};